package uk.ac.manchester.cs.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
 * <p>
 * Title: SetUtils
 * </p>
 * <p>
 * Description: Provides basic set utility functions including generation of
 * random subsets
 * </p>
 * <p>
 * Copyright: Copyright (c) 2007, 2008
 * </p>
 * <p>
 * Company: Clark & Parsia, LLC. <http://www.clarkparsia.com>
 * </p>
 * 
 * @author Pavel Klinov
 */
public class SetUtils {

	public static void main(String[] args) {

		 System.out.println(kSubsets(Arrays.asList(new Integer[] {1, 2, 3, 4, 5}), 3));
	}

	/**
	 * Compute all unordered subsets of the length k.
	 * 
	 * @param list
	 * @param k
	 * @return
	 */
	public static <T> Set<Set<T>> kSubsets(List<T> list, int k) {

		long max = numOfSubsets( list.size(), k );
		Set<Set<T>> result = new HashSet<Set<T>>( (int) max );

		for( int index = 0; index < max; index++ ) {
			result.add( subset( list, k, index ) );
		}

		return result;
	}

	public static long numOfSubsets(int size, int k) {

		if( (0 == k) || (size == k) ) {

			return 1;
		}

		return numOfSubsets( size - 1, k - 1 ) + numOfSubsets( size - 1, k );
	}

	public static <T> Set<T> subset(List<T> list, int k, long index) {

		int size = list.size();
		Set<T> result = new HashSet<T>();

		for( int slotValue = 1; slotValue <= size; slotValue++ ) {
			if( 0 == k ) {
				break;
			}

			long threshold = numOfSubsets( size - slotValue, k - 1 );

			if( index < threshold ) {
				// System.out.print( list.get(slotValue - 1) + "\t" );
				result.add( list.get( slotValue - 1 ) );
				k--;
			} else if( index >= threshold ) {
				index = index - threshold;
			}
		}

		// System.out.println();
		return result;
	}

	public static <T> void printAll(List<T> list, int k) {

		long max = numOfSubsets( list.size(), k );

		for( int index = 0; index < max; index++ ) {
			subset( list, k, index );
		}
	}

	/*
	 * Computes intersection of a collection of sets
	 */
	public static <T> Set<T> intersection(Collection<Set<T>> sets) {

		Set<T> result = new HashSet<T>();
		result.addAll( sets.iterator().next() );

		for( Set<T> set : sets ) {

			result.retainAll( set );
		}

		return result;
	}

	public static <T> Set<T> intersection(Collection<T>... sets) {

		Set<T> result = new HashSet<T>();
		result.addAll( sets[0] );

		for( int i = 1; i < sets.length; i++ )
			result.retainAll( sets[i] );

		return result;
	}
	
	public static <T> Set<T> difference(Set<? extends T> first, Set<? extends T> second) {
		
		Set<T> result = new HashSet<T>(first);
		
		result.removeAll(second);
		
		return result;
	}

	/*
	 * Randomly picks an element from the set
	 */
	public static <T> T pickRandomElement(Set<T> set) {

		int rnd = (int) (Math.random() * (set.size() - 1));
		Iterator<T> iter = set.iterator();
		T result = iter.next();

		for( ; rnd > 0; rnd-- ) {

			result = iter.next();
		}

		return result;
	}

	public static <T> Set<T> pickRandomSubset(Collection<T> set, int size) {
		
		return pickRandomSubset(set, size, new Random());
	}
	
	/*
	 * Selects a random subset of the given size
	 */
	public static <T> Set<T> pickRandomSubset(Collection<T> set, int size, Random rnd) {

		List<T> list = set instanceof List
			? (List<T>) set
			: new ArrayList<T>( set );

		Collections.shuffle( list, rnd );

		if( size >= set.size() ) {

			return new HashSet<T>( set );
		}

		Set<T> subset = new HashSet<T>( size );

		for( int i = 0; i < size; i++ ) {

			subset.add( list.get( i ) );
		}

		return subset;
	}

	/**
	 * Returns a random binary relation over the set This method should only be
	 * used if num is much smaller than the size of the Cartesian product
	 * 
	 * @param set
	 *            Given set
	 * @param num
	 *            Relation's cardinality
	 * @param antiRefl
	 *            If the relation must be anti-reflexive
	 * @return
	 */
	public static <T> Set<List<T>> pickRandomRelation(Set<T> set, int num, boolean antiRefl) {

		List<T> list = new ArrayList<T>( set );
		Set<List<T>> rel = new HashSet<List<T>>( num );
		Set<Integer> previousPairIndexes = new HashSet<Integer>( num );
		Random rnd = new Random();
		int cartesianSize = set.size() * set.size();
		int pairIndex = -1;
		int firstIndex = -1;
		int secondIndex = -1;

		while( rel.size() < num ) {

			do {

				pairIndex = rnd.nextInt( cartesianSize );
				firstIndex = pairIndex / set.size();
				secondIndex = pairIndex % set.size();

			} while( previousPairIndexes.contains( pairIndex )
					|| (antiRefl && (firstIndex == secondIndex)) );

			previousPairIndexes.add( pairIndex );
			{
				List<T> pair = new ArrayList<T>( 2 );

				pair.add( list.get( firstIndex ) );
				pair.add( list.get( secondIndex ) );
				rel.add( pair );
			}
		}

		return rel;
	}

	/*
	 * WARNING: the function does not check that there exist that many subsets
	 * of the given size. Checking would require computing of a binomial
	 * coefficient which might be slow. Other approximations might be used (see
	 * Stirling approximation for example). Currently the function stops after
	 * stumbling over a number of duplicates
	 */
	public static <T> Set<Set<T>> pickRandomSubsets(Set<T> set, int size, int number) {

		Set<Set<T>> subsets = new HashSet<Set<T>>( number );
		int dups = 0;

		if( size > set.size() ) {

			return null;
		}

		while( subsets.size() < number && dups < set.size() ) {

			if( !subsets.add( pickRandomSubset( set, size ) ) ) {

				dups++;

			} else {

				dups = 0;
			}
		}

		return subsets;
	}

	/*
	 * Computes binomial coefficient (n,k)
	 */
	public static int biCoeff(int n, int k) {

		if( (0 == k) || (n == k) ) {

			return 1;
		}

		return biCoeff( n - 1, k - 1 ) + biCoeff( n - 1, k );
	}

	public static <T> Set<T> union(Set<T> set1, Set<T> set2) {
		
		Set<T> result = new HashSet<T>(set1);
		
		result.addAll(set2);
		
		return result;
	}
	
	public static <T> Set<T> union(Collection<Set<T>> sets) {
		
		Set<T> result = new HashSet<T>();
		
		for (Set<T> set : sets) result.addAll(set);
		
		return result;
	}
	
	/*
     * Adds sets to the set of sets and makes sure that the resulting sets are all minimal w.r.t. set inclusion
     * 
     */
	public static <T> void addAllandMinimizeWrtInclusion(Collection<Set<T>> addedSets,	Collection<Set<T>> sets) {
		
		for (Set<T> set : addedSets) addAndMinimizeWrtInclusion(set, sets);
	}
    /*
     * Adds a set to the set of sets and makes sure that the resulting sets are all minimal w.r.t. set inclusion
     * 
     * TODO Needs testing
     */
	public static <T> void addAndMinimizeWrtInclusion(Set<T> set, Collection<Set<T>> sets) {

		//Set<Set<T>> toRemove = new HashSet<Set<T>>();

		if (set.isEmpty()) {
			//Empty set is always the minimal
			sets.clear();
			sets.add(set);
			
			return;
		}
		
		for (Iterator<Set<T>> iter = sets.iterator(); iter.hasNext();) {
			
			Set<T> existing = iter.next();
			
			if (set.containsAll(existing)) {

				return; // No need to add this one
			}

			if (existing.containsAll(set)) { // Need to remove an existing set

				iter.remove();
			}
		}
		
		sets.add(set);
	}
	
	public static <T> Set<T> union(Collection<T>... cols) {
		
		Set<T> union = new HashSet<T>();
		
		for (Collection<T> coll : cols) union.addAll(coll);
		
		return union;
	}
	
	/*
	 * Unions every set in the first collection with every set in the second collection
	 * 
	 * TODO The implementation is horribly inefficient!
	 */
	public static <T> Collection<Set<T>> unionAllAndMinimizeWrtInclusion(Collection<Set<T>> sets1, Collection<Set<T>> sets2) {
		
		Collection<Set<T>> result = new ArrayList<Set<T>>();
		
		for (Set<T> set1 : sets1) {
			
			for (Set<T> set2 : sets2) {
				
				addAndMinimizeWrtInclusion(union(set1, set2), result);
			}
		}
		
		return result;
	}
	
	public static <T> Collection<Set<T>> unionAndMinimizeWrtInclusion(Collection<Set<T>> sets, Set<T> set) {
		
		Collection<Set<T>> result = new ArrayList<Set<T>>();
		
		for (Set<T> elemSet : sets) {
				
			addAndMinimizeWrtInclusion(SetUtils.union(elemSet, set), result);
		}
		
		return result;
	}

	public static <T> boolean containsSubset(Collection<Set<T>> sets, Set<T> set) {
		
		return containsSubset(sets, set, false);
	}
	
	public static <T> boolean containsSubset(Collection<Set<T>> sets, Set<T> set, boolean proper) {

		for (Set<T> elemSet : sets) {
			
			if (set.containsAll(elemSet) && (!proper || set.size() > elemSet.size())) return true;
		}
		
		return false;
	}

	public static <T> boolean containsSuperset(Collection<Set<T>> sets, Set<T> set) {
		
		return containsSuperset(sets, set, false);
	}

	public static <T> boolean containsSuperset(Collection<Set<T>> sets, Set<T> set, boolean proper) {

		for (Set<T> elemSet : sets) {
			
			if (elemSet.containsAll(set) && (!proper || elemSet.size() > set.size())) return true;
		}
		
		return false;
	}
}
